from heapq import heapify, heappop

Infinity = float('inf')  # lol, there's an infinity representation in python


def extract_min(Q):
	heapify(Q)
	return heappop(Q)


def mst_prim(G, w, s):
	S = []  # S is the solution set that will store edges of PRIM MST
	P = dict()
	for r in G.vertices:
		r.key = Infinity
		P[r] = None
	s.key = 0
	Q = G.vertices
	while len(Q) != 0:
		u = extract_min(Q)
		if P[u] is not None:
			S.append((P[u], u))
		for r in G.adjacencies(u):
			if r in Q and w((u, r)) < r.key:
				P[r] = u
				r.key = w((u, r))
	return S
